package TwentyThirdDay;

public class SearchInsert {
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        if (nums[0] >= target){
            return 0;
        } else if (nums[right] <= target) {
            return right + 1;
        }
        int mid;
        while (left < right){
            mid = (left + right) / 2;
            if (mid == left){
                return right;
            }
            if (nums[mid] == target){
                return mid;
            } else if (nums[mid] < target) {
                left = mid;
            }else {
                right = mid;
            }
        }
        if (nums[left] < target){
            return left + 1;
        }else {
            return left;
        }
    }
}
